
//611.有效三角形的个数
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        //此题可以采用固定最小边a，求另外两条边b,c;需要满足c-b<a
        //所以b和c之间的距离不能太大，所以可以使用同向双指针
        int n=nums.size(),ret=0;
        sort(nums.begin(),nums.end());
        for(int i=0;i<n-2;i++)
        {
            int a=nums[i];
            if(a==0) continue;   //对于长度为0的边不能参与计数
            //进行同向双指针
            int count=0,left=i+1;
            for(int right=i+2;right<n;right++)
            {
                while(left<right&&nums[right]-nums[left]>=a) left++;
                count+=right-left;
            }
            ret+=count;
        }
        return ret;
    }
};